package com.lwl.leetcode;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @author lwl
 * @Description 给你一个链表数组，每个链表都已经按升序排列。
 * <p>
 * 请你将所有链表合并到一个升序链表中，返回合并后的链表
 * @date 2023/7/28 15:26
 */
public class Code23MergeKLists {

    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }
        PriorityQueue<ListNode> minHeap = new PriorityQueue<>(Comparator.comparingInt(o -> o.val));
        ListNode res = new ListNode();
        ListNode t = res;
        for (int i = 0; i < lists.length; i++) {
            if (lists[i] != null) {
                minHeap.add(lists[i]);
            }
        }
        while (!minHeap.isEmpty()) {
            ListNode node = minHeap.poll();
            t.next = node;
            if (node.next != null) {
                node = node.next;
                minHeap.add(node);
            }
            t = t.next;
        }
        return res.next;
    }

}
